import java.util.ArrayList;
import java.util.List;

public class Solution715 {

    List<int[]> list=new ArrayList<>();

    public Solution715() {

    }

    public void addRange(int left, int right) {
        if (list.isEmpty() || left>list.get(list.size()-1)[1]){
            list.add(new int[]{left,right});
            return;
        }
        int l=0,r=list.size()-1,ans=-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (left<=list.get(mid)[1]){
                ans=mid;
                r=mid-1;
            }else {
                l=mid+1;
            }
        }
        if (right<list.get(ans)[0]){
            list.add(ans,new int[]{left,right});
            return;
        }
        int start=Math.min(left,list.get(ans)[0]);
        int t=ans+1;
        while (t<list.size() && right>=list.get(t)[0]){
            t++;
        }
        int end=Math.max(right,list.get(t-1)[1]);
        for (int i=0;i<t-ans;i++){
            list.remove(ans);
        }
        list.add(ans,new int[]{start,end});
    }

    public boolean queryRange(int left, int right) {
        if (list.isEmpty() || left>list.get(list.size()-1)[1]){
            return false;
        }
        int l=0,r=list.size()-1,ans=-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (left<=list.get(mid)[1]){
                ans=mid;
                r=mid-1;
            }else {
                l=mid+1;
            }
        }
        return left>=list.get(ans)[0] && right <= list.get(ans)[1];
    }

    public void removeRange(int left, int right) {
        if (list.isEmpty() || left>list.get(list.size()-1)[1]){
            return;
        }
        int l=0,r=list.size()-1,ans=-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (left<=list.get(mid)[1]){
                ans=mid;
                r=mid-1;
            }else {
                l=mid+1;
            }
        }
        if (right<list.get(ans)[0]){
            return;
        }
        if (left>list.get(ans)[0]){
            list.add(ans,new int[]{list.get(ans)[0],left});
            ans++;
        }
        int t=ans+1;
        while (t<list.size() && right>=list.get(t)[0]){
            t++;
        }
        if (right<list.get(t-1)[1]){
            list.add(t,new int[]{right,list.get(t-1)[1]});
        }
        for (int i=ans;i<=t-1;i++){
            list.remove(ans);
        }
    }


    public static void main(String[] args) {
        Solution715 solution715=new Solution715();
        solution715.addRange(10,20);
        solution715.removeRange(14,16);
        System.out.println(solution715.queryRange(10,14));
        System.out.println(solution715.queryRange(13, 15));
        System.out.println(solution715.queryRange(16, 17));
    }
}
